import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}




public class prog {
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
        int ret=dfs(root,targetSum);
        ret+=pathSum(root.left,targetSum);
        ret+=pathSum(root.right,targetSum);
        return ret;
    }
    public int dfs(TreeNode root,int key){
        if(root==null){
            return 0;
        }
        int ret=0;
        int val=root.val;
        if(key==val){
            ret++;
        }
        ret+=dfs(root.left,key-val);
        ret+=dfs(root.right,key-val);
        return ret;
    }












    public int pathSum1(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
        int ret=dfs3(root,targetSum);
        ret+=pathSum1(root.left,targetSum);
        ret+=pathSum1(root.right,targetSum);
        return ret;
    }
    public int dfs3(TreeNode root,int key){
        int ret=0;
        if(root==null){
            return 0;
        }
        int val=root.val;
        if(key==val){
            ret++;
        }
        ret+=dfs3(root.left,key-val);
        ret+=dfs3(root.right,key-val);
        return ret;
    }














    public int findMinDifference(List<String> timePoints) {
        if(timePoints.size()>24*60){
            return 0;
        }
        List<Integer> list=new LinkedList<>();
        for(String s:timePoints){
            String[] str=s.split(":");
            list.add(Integer.parseInt(str[0])*60+Integer.parseInt(str[1]));
        }
        int min=24*60;
        Collections.sort(list);
        list.add(list.get(0)+24*60);
        for(int i=1;i<list.size();i++){
            min=Math.min(min,list.get(i)-list.get(i-1));
        }
        return min;
    }














    public int findMinDifference1(List<String> timePoints) {
        if(timePoints.size()>24*60){
            return 0;
        }
        List<Integer> list=new LinkedList<>();
        for(String s: timePoints){
            String[] str=s.split(":");
            list.add(Integer.parseInt(str[0])*60+Integer.parseInt(str[1]));
        }
        Collections.sort(list);
        list.add(list.get(0)+24*60);
        int min=24*60;
        for(int i=1;i<list.size();i++){
            min=Math.min(min,list.get(i)-list.get(i-1));
        }
        return min;
    }














    List<List<Integer>> list=new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len=nums.length;
        Arrays.sort(nums);
        Deque<Integer> deque=new ArrayDeque<>();
        boolean[] booleans=new boolean[len];
        dfs2(nums,0,len,deque,booleans);
        return list;
    }
    public void dfs2(int[] arr,int start,int end,Deque<Integer> deque,boolean[] booleans){
        if(start==end){
            list.add(new LinkedList<>(deque));
            return ;
        }
        for(int i=0;i<end;i++){
            if(booleans[i]){
                continue;
            }
            if(i>0&&arr[i]==arr[i-1]&&!booleans[i-1]){
                continue;
            }
            deque.addLast(arr[i]);
            booleans[i]=true;
            dfs2(arr,start+1,end,deque,booleans);
            booleans[i]=false;
            deque.removeLast();
        }
    }














    List<List<Integer>> list1=new LinkedList<>();
    public List<List<Integer>> permuteUnique1(int[] nums) {
        Deque<Integer> deque=new ArrayDeque<>();
        Arrays.sort(nums);
        int len=nums.length;
        boolean[] booleans=new boolean[len];
        dfs1(nums,0,nums.length,deque,booleans);
        return list1;
    }
    public void dfs1(int[] arr,int start,int end,Deque<Integer> deque,boolean[] booleans){
        if(start==end){
            list1.add(new LinkedList<>(deque));
            return ;
        }
        for(int i=0;i<end;i++){
            if(booleans[i]){
                continue;
            }
            if(i>0&&arr[i]==arr[i-1]&&!booleans[i-1]){
                continue;
            }
            deque.addLast(arr[i]);
            booleans[i]=true;
            dfs1(arr,start+1,end,deque,booleans);
            booleans[i]=false;
            deque.removeLast();
        }
    }










    public int minFlipsMonoIncr(String s) {
        int dp=0;
        int sum=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='1'){
                sum++;
            }else{
                dp=Math.min(dp+1,sum);
            }
        }
        return dp;
    }










    public int minFlipsMonoIncr1(String s) {
        int dp=0;
        int sum=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='1'){
                sum++;
            }else{
                dp=Math.min(dp+1,sum);
            }
        }
        return dp;
    }








    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }












    public int uniquePaths1(int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }












    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}
